Previous calculations of induction variables have been limited in the scope or ease of determination of induction variables which they could find, and have been limited to finding induction variables when they occur as user variables.
A recent paper "Beyond Induction Variables" by Michael Wolfe, ACM Sigplan 92, p. 162 describes a prior state-of-the-art method for computing induction variables. His analysis uses the static-single-assignment form.
The work of Wolfe has several limitations: it is limited to a sequence of assignments of the form
Scalar=Scalar+constant,
as stated on p. 165 of Wolfe's teachings. The disadvantages of this form is that it is not very general and misses a large amount of induction variables when an assignment is not of the form Scalar=Scalar+constant. For Wolfe, the right-hand side may have only one term, and its coefficient is unity. A need exists to allow much more general linear combinations which allow multiple terms on the right-hand side with different integer constants/coefficients.
While Wolfe's work does make it possible to find quadratic induction variables, his method works only in the presence of the restriction noted above and requires the solution of matrix equations. Similarly, Wolfe's analysis is able to determine some geometric induction variables, but only by setting up and solving equations to find coefficients of powers of induction variables.
Further, Wolfe's method is able to look for flip-flop induction variables, but again with the restrictions noted above. In addition, this is a special case to be looked for.
Wolfe's methods also use methods which require generation of inverse matrices of integer matrices. Since his matrices are not unimodular matrices, his methods introduce fractions when the inverse matrix is computed. Fractions should be avoided as much as is possible and is a disadvantage of Wolfe's method.
Finally, Wolfe's methods don't find induction variables when the user's original variables are not induction variables. This is a severe limitation to Wolfe's method.
The paper "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Ron Cytron, Jeanne Ferrante, Barry K. Rosen and Mark N. Wegman, ACM Transactions on Programming Languages and Systems, 13 (1991) p. 451, is a help in understanding the work described by Wolfe.